package dataStrcture;

import java.util.Random;
import java.util.Stack;

/**
 * 单调栈
 * Created by shuowu on 2017/10/18.
 */
public class MonotonousStack {


//    public static void main(String[] args){
//        long time  = System.currentTimeMillis();
//        try {
//            Thread.sleep(5000);
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }
//        System.out.println( (System.currentTimeMillis() - time) + " ms");
//    }

    public static void main(String[] args){
        int[] nums = {5, 4, 3, 3, 1};
        System.out.println(findUnsortedSubArray(nums));
    }
//    public static void main(String[] args){
//        Random random = new Random();
//        int[] nums = new int[20];
//        for(int i = 0; i < nums.length; i++){
//            nums[i] = random.nextInt(100);
//        }
//        for (int num : nums) {
//            System.out.print(" " + num);
//        }
//        System.out.println();
//        getFirstMin(nums);
//    }

    //求左边第一个比当前值小的值
    public static void getFirstMin(int[] nums){
        if(nums == null || nums.length <= 0){
            return;
        }
        Stack<Integer> stack = new Stack<>();
        int[] leftLess = new int[nums.length];
        int stackBottom = -1;
        for(int i = 0; i < nums.length; i++){
            //如果
            if(stack.isEmpty() || stack.peek() < nums[i]){
                if(stack.isEmpty()){
                    leftLess[i] = -1;
                    stackBottom = nums[i];
                } else{
                    //否则左边第一个比她小的元素就是栈底的元素
                    leftLess[i] = stack.peek();
                }
                stack.push(nums[i]);
            } else {
                while(!stack.isEmpty() && stack.peek() > nums[i]){
                    stack.pop();
                }
                //如果此时栈是空的，那么就是不存在左边比他小的值
                if(stack.isEmpty()){
                    leftLess[i] = -1;
                    stackBottom = nums[i];
                } else {
                    leftLess[i] = stack.peek();
                }
                stack.push(nums[i]);
            }
        }
        for (int num : leftLess) {
            System.out.print(" " + num);
        }
    }

    public static int findUnsortedSubArray(int[] nums) {
        if(nums == null || nums.length <= 0){
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int left = Integer.MAX_VALUE;
        int right = 0;
        for(int i = 0; i < nums.length; i++){
            if(stack.isEmpty() || nums[stack.peek()] <= nums[i]){
                stack.push(i);
            }else {
                while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                    stack.pop();
                }
                if(stack.isEmpty()){
                    left = 0;
                }  else {
                    left = Math.min(left, stack.peek() + 1);
                    System.out.println("cur i: " + i + " stack " +  stack.peek() + "left: " + left);
                }
                //left = stack.isEmpty() ? 0 : stack.peek() + 1;
            }
        }
        stack.clear();
        for(int i = nums.length - 1; i >= 0; i--){
            if(stack.isEmpty() || nums[stack.peek()] >= nums[i]){
                stack.push(i);
            }else {
                while(!stack.isEmpty() && nums[stack.peek()] < nums[i]){
                    stack.pop();
                }
                if(stack.isEmpty()){
                    right = nums.length - 1;
                }  else {
                    right = Math.max(right, stack.peek() - 1);
                    System.out.println("cur i: " + i + " stack " +  stack.peek() + "right: " + right);
                }
                //right = stack.isEmpty() ? nums.length - 1 : stack.peek() - 1;
            }
        }
        if(left == Integer.MAX_VALUE){
            left = 1;
        }
        return right - left + 1;
    }

    public int findUnsortedSubarray(int[] nums) {
        int i = 0, j = -1, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

        for (int l = 0, r = nums.length - 1; r >= 0; l++, r--) {
            max = Math.max(max, nums[l]);
            if (nums[l] != max) j = l;

            min = Math.min(min, nums[r]);
            if (nums[r] != min) i = r;
        }

        return (j - i + 1);
    }
}
